#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>

int const maxn = 10002;
int color[maxn], used[maxn];
bool vis[maxn];
int n, m, k;

int graph[maxn][100];

void dfs(int x, std::stack<int> & ds)
{
	vis[x] = true;
	for (int i = 0; i <= graph[x][0]; i++) {
		int v = graph[x][i];
		if (!vis[v]) dfs(v, ds);
	}
	ds.push(x);
}

void color_it()
{
	for (int i = 0; i < n; i++) {
		vis[i] = false; color[i] = -1; used[i] = 0;
	}
	std::stack<int> dfs_squence;

	for (int i = 0; i < n; i++)
		if (!vis[i]) dfs(i, dfs_squence);

	int now = 0;
	for (int i = n - 1; i >= 0; i--) {
		int u = dfs_squence.top();
		dfs_squence.pop();
		now++;
		for (int j = 0; j <= graph[u][0]; j++) {
			int v = graph[u][j];
			if (color[v] >= 0)
				used[color[v]] = now;
		}
		for (int j = 0; j < k; j++) {
			if (used[j] != now)
				color[u] = j;
		}
	}
}

int main()
{
	int T;
	std::scanf("%d", &T);
	while (T--) {
		std::scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++)
			graph[i][0] = 0;

		for (int i = 0, x, y; i < m; i++) {
			std::scanf("%d%d", &x, &y);
			x--; y--;
			graph[x][++graph[x][0]] = y;
			graph[y][++graph[y][0]] = x;
		}

		k = 0;
		for (int i = 0; i < n; i++)
			k = std::max(k, graph[i][0]);
		if (!(k & 1)) k++;

		color_it();
		std::printf("%d\n", k);
		for (int i = 0; i < n; i++)
			std::printf("%d\n", color[i] + 1);
		printf("\n");
	}
}

